package org.cxy;

import java.util.*;

//N皇后问题（返回所有解）
public class NQueens {

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        
        // 初始化棋盘，全部为空格 '.'
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }

        // 标记列、主对角线、次对角线是否已有皇后
        boolean[] cols = new boolean[n];           // 列
        boolean[] diags1 = new boolean[2 * n - 1]; // 主对角线: row - col + n - 1
        boolean[] diags2 = new boolean[2 * n - 1]; // 次对角线: row + col

        backtrack(result, board, 0, n, cols, diags1, diags2);
        return result;
    }

    private void backtrack(List<List<String>> result, char[][] board, int row, int n,
                           boolean[] cols, boolean[] diags1, boolean[] diags2) {

        // 结束条件：已经处理完所有行
        if (row == n) {
            result.add(constructBoard(board));
            return;
        }

        // 尝试当前行的每一列
        for (int col = 0; col < n; col++) {
            int d1 = row - col + n - 1; // 主对角线索引
            int d2 = row + col;         // 次对角线索引

            // 如果该位置会被攻击，则跳过
            if (cols[col] || diags1[d1] || diags2[d2]) {
                continue;
            }

            // 做选择：放置皇后
            board[row][col] = 'Q';
            cols[col] = true;
            diags1[d1] = true;
            diags2[d2] = true;

            // 进入下一行
            backtrack(result, board, row + 1, n, cols, diags1, diags2);

            // 撤销选择：回溯
            board[row][col] = '.';
            cols[col] = false;
            diags1[d1] = false;
            diags2[d2] = false;
        }
    }

    // 将 char[][] 转换为 List<String>
    private List<String> constructBoard(char[][] board) {
        List<String> res = new ArrayList<>();
        for (char[] row : board) {
            res.add(new String(row));
        }
        return res;
    }

    // 测试示例
    public static void main(String[] args) {
        NQueens solver = new NQueens();
        int n = 4;
        List<List<String>> solutions = solver.solveNQueens(n);

        System.out.println("N = " + n + " 时共有 " + solutions.size() + " 个解：\n");
        for (int i = 0; i < solutions.size(); i++) {
            System.out.println("解 " + (i + 1) + ":");
            for (String row : solutions.get(i)) {
                System.out.println(row);
            }
            System.out.println();
        }
    }
}